/**
 * 买卖股票的最佳时机-多次买卖，只能持有一只
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。
你在任何时候 **最多** 只能持有 **一股** 股票。你也可以先购买，然后在 **同一天** 出售。
返回 你能获得的 **最大** 利润 。
输入：prices = [7,1,5,3,6,4]
输出：7
 */
var maxProfit = function(prices) {
  const m = prices.length;
  const dp = Array(m).fill([0,0]);
  dp[0] = [-prices[0], 0];
  for(let i=1; i<m; i++) {
    dp[i] = [
      Math.max(dp[i-1][0], dp[i-1][1]-prices[i]),
      Math.max(dp[i-1][1], dp[i-1][0]+prices[i])
    ]
  }
  return dp[m-1][1];
};
const prices = [7,1,5,3,6,4];
console.log('买卖股票的最佳时机-多次买卖，只能持有一只', maxProfit(prices)); //7

/**
 * 优化一维数组
 */
var maxProfit = function(prices) {
  const dp = Array(3).fill(0);
  dp[1] = -prices[0];
  for(let i=1;i<prices.length;i++) {
    dp[1] = Math.max(dp[1], dp[2]-prices[i]);
    dp[2] = Math.max(dp[2], dp[1]+prices[i]);
  }
  return dp[2];
}
console.log('买卖股票的最佳时机-多次买卖，只能持有一只', maxProfit(prices)); //7

/**
 * 贪心 区间的利润=连续利润和
 * 利润拆分=每天都是最优--全局就是最优的
 * 【证明】这个贪心算法的正确性可以通过反证法来证明。
 * 假设存在一个更优的策略，能够获得比贪心算法更高的利润。
 * 那么这个策略在某一天 i 上的操作一定与贪心算法不同。
 * 但是，由于贪心算法在每一天都选择了当前状态下最优的操作，
 * 所以这个不同的操作不可能带来更高的利润。
 * 因此，贪心算法是最优的
 */
var maxProfit01 = function (prices) {
  let resProfit = 0;
  for (let i = 1; i < prices.length; i++) {
    resProfit += Math.max(prices[i] - prices[i - 1], 0);
  }
  return resProfit;
};
console.log('买卖股票的最佳时机-贪心', maxProfit(prices)); //7
